/**
 * 给你一个字符串 s，由小写英文字母和特殊字符：'*'、'#' 和 '%' 组成。

同时给你一个整数 k。

请根据以下规则从左到右处理 s 中每个字符，构造一个新的字符串 result：

如果字符是 小写 英文字母，则将其添加到 result 中。
字符 '*' 会 删除 result 中的最后一个字符（如果存在）。
字符 '#' 会 复制 当前的 result 并追加到其自身后面。
字符 '%' 会 反转 当前的 result。
返回最终字符串 result 中第 k 个字符（下标从 0 开始）。如果 k 超出 result 的下标索引范围，则返回 '.'。

1 <= s.length <= 10^5
s 只包含小写英文字母和特殊字符 '*'、'#' 和 '%'。
0 <= k <= 10^15
处理 s 后得到的 result 的长度不超过 10^15。

 */

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>

using namespace std;
class Solution
{
public:
    char processStr(string s, long long k)
    {
        vector<pair<char, long long>> history;
        long long len = 0;

        for (char c : s)
        {
            if (islower(c))
            {
                history.push_back({c, len});
                len++;
            }
            else if (c == '*')
            {
                if (len > 0)
                {
                    history.push_back({c, len});
                    len--;
                }
            }
            else if (c == '#')
            {
                history.push_back({c, len});
                if (len > 0)
                {
                    len *= 2;
                }
            }
            else if (c == '%')
            {
                history.push_back({c, len});
            }
        }

        if (k >= len)
        {
            return '.';
        }

        for (int i = history.size() - 1; i >= 0; --i)
        {
            char op = history[i].first;
            long long prev_len = history[i].second;

            if (islower(op))
            {
                if (k == prev_len)
                {
                    return op;
                }
            }
            else if (op == '*')
            {
                //
            }
            else if (op == '#')
            {
                if (k >= prev_len)
                {
                    k %= prev_len;
                }
            }
            else if (op == '%')
            {
                k = prev_len - 1 - k;
            }
        }

        return '.';
    }
};